﻿using SortingNetworkSimulator.Model;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingNetworkSimulator.Creators
{
    class BitonicSorter
    {
        public List<ComparatorData> Comparators;
        private Network network { get; set; }

        public BitonicSorter(Network network)
        {
            this.network = network;
            this.Comparators = new List<ComparatorData>();
        }

        public Network Transform()
        {
            sort(0, network.InputsCount);

            foreach (ComparatorData comparatorData in Comparators.OrderBy(p => p.Layer))
            {
                network.AddComparator(comparatorData.WireOneIndex, comparatorData.WireTwoIndex, comparatorData.Layer);
            }

            return network;
        }

        private void sort(int start, int inputsCount)
        {
            if (inputsCount > 1)
            {
                int mid = inputsCount / 2;
                sort(start, mid);
                sort(start+mid, mid);
                merge(start, inputsCount, 1);
            }
        }

        private void merge(int lo, int n, int r)
        {
            int m = r * 2;
            if (m < n)
            {
                merge(lo, n, m);
                merge(lo + r, n, m);
                for (int i = lo + r; i + r < lo + n; i += m)
                    compare(i, i + r);
            }
            else
                compare(lo, lo + r);
        }

        private void compare(int i, int j)
        {
            ComparatorData cd;
            cd.WireOneIndex = i;
            cd.WireTwoIndex = j;
            cd.Layer = -1;

            var max = this.Comparators.OrderByDescending(p => p.Layer).FirstOrDefault().Layer;
            int k;
            for (k = max; k >= 0; k--)
            {
                if (Comparators.Count == 0)
                {
                    cd.Layer = 0;
                    break;
                }
                foreach (ComparatorData cda in Comparators.Where(p => p.Layer == k))
                {
                    if (cda.WireOneIndex == i || cda.WireTwoIndex == j ||
                        cda.WireOneIndex == j || cda.WireTwoIndex == i){
                        cd.Layer = k+1;
                        break;
                    }
                }
                if (cd.Layer != -1)
                    break;
            }
            if (cd.Layer == -1)
                cd.Layer = k+1;
            this.Comparators.Add(cd);
        }

    }
}
